package fun.coding.leetcode;

import java.util.Arrays;
import java.util.Comparator;

public class LargestNumber {

	public static void main(String[] args) {
		String[] s1 = {"a", "ab", "ac", "abb"};
		Arrays.sort(s1);
		
		// lexicographically order is 3, 30, 33, 4 
		String[] s2 = {"4", "3", "30", "33"};
		Arrays.sort(s2);
		
		LargestNumber ins = new LargestNumber();
		
		int[] test6 = {824, 8247};
		System.out.println(ins.largestNumber(test6));
		
		int[] test1 = {3, 30, 34, 5, 9};
		//int[] test1 = {3, 30};
		System.out.println(ins.largestNumber(test1));
		
		int[] test2 = {0, 0, 0, 0};
		System.out.println(ins.largestNumber(test2));
		
		int[] test3 = {3, 3};
		System.out.println(ins.largestNumber(test3));
		
		int[] test4 = {121, 12};
		System.out.println(ins.largestNumber(test4));
		
		int[] test5 = {128, 12};
		System.out.println(ins.largestNumber(test5));
	}
	
	public String largestNumber(int[] num) {
		StringBuilder sb = new StringBuilder();
		
		if (num == null || num.length == 0) return sb.toString();
		
		String[] nums = new String[num.length];
		for (int i = 0; i < num.length; i++) {
			nums[i] = String.valueOf(num[i]);
		}
		
		LargestNumberComparator c = new LargestNumberComparator();
		Arrays.sort(nums, c);
		
		for (int i = nums.length -1 ; i >= 0; i--) {
			sb.append(nums[i]);
		}
		
		String res = sb.toString();
		
		if (res.charAt(0) == '0' && res.length() > 1) return "0";
		
		return res;
	}
	
	private class LargestNumberComparator implements Comparator<String> {
		@Override
		public int compare(String o1, String o2) {
			if (o1.equals(o2)) return 0;
			
			// Just need to compare o1o2 and o2o1, very smart!
			String o1o2 = o1 + o2;
			String o2o1 = o2 + o1;
			
			return o1o2.compareTo(o2o1) > 0 ? 1 : -1;
		}
	}
	
	
	/* This implementation makes the problem too complicated, 
	 * should take advantage of the string lexicographically comparison, naturally "34" > "235", saves lots of integer massage
	private class LargestNumberComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {
			if (o1 == o2) return 0;
			
			int originalO1 = o1;
			int originalO2 = o2;
			
			int d1 = getTotalDigits(o1);
			int d2 = getTotalDigits(o2);
			
			int h1 = 0;
			int h2 = 0;
			while (d1 > 0 && d2 > 0) {
				h1 = o1 / (int)Math.pow(10, d1 - 1);
				h2 = o2 / (int)Math.pow(10, d2 - 1);
				if (h1 > h2) {
					return 1;
				} else if (h1 < h2) {
					return -1;
				} else {
					o1 -= h1*(int)Math.pow(10, d1-1);
					o2 -= h2*(int)Math.pow(10, d2-1);
					d1--;
					d2--;
				}
			}
			
			if (d1 == 0 && d2 != 0) {
				return (o2 / (int)Math.pow(10, d2 - 1)) > originalO1 % 10 ? -1 : 1;
			} else if (d1 != 0 && d2 == 0){
				return (o1 / (int)Math.pow(10, d1 - 1)) > originalO2 % 10 ? 1 : -1;
			} else if (d1 == 0 && d2 == 0) {
				// should not reach here
				return 0;
			} else {
				// should not reach here
				return -100;
			}
		}
		
		private int getTotalDigits(int n) {
			int totalDigits = 0;
			
			while (n != 0) {
				n = n / 10;
				totalDigits++;
			}
			return totalDigits;
		}
	}
	*/
}
